PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmhash.cpp

C/C++ Source or Header | 1994-09-06 | 9.8 KB | 405 lines

// CmHash.cpp
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Hash table implementation.
// -----------------------------------------------------------------

#include <cm/include/cmhash.h>


// "CmHashTable" is the default table constructor.
//
CmHashTable::CmHashTable(unsigned sz)
{
  _total   = 0;
  _buckets = new CmHashBucket[sz];
  _size    = (_buckets != NULL) ? sz : 0;
}


// "CmHashTable" is the table copy constructor.
//
CmHashTable::CmHashTable(const CmHashTable& T)
{
  _total   = 0;
  _buckets = new CmHashBucket[T._size];
  _size    = (_buckets != NULL) ? T._size : 0;
  copy(T);
}


// "CmHashTable" is the table destructor.
//
CmHashTable::~CmHashTable()
{
  removeAll();
  delete[] _buckets;
}


// "=" assignment operator copies the contents of the specified
// table into this table.
//
CmHashTable& CmHashTable::operator=(const CmHashTable& T)
{
  if (&T != this)
  {
    removeAll();
    delete[] _buckets;
    _total   = 0;
    _buckets = new CmHashBucket[T._size];
    _size    = (_buckets != NULL) ? T._size : 0;
    copy(T);
  }
  return *this;
}


// "add" adds the specified object to the hash table.
//
Bool CmHashTable::add(CmObject* pObj)
{
  if (!pObj) return FALSE;
  Bool success = _buckets[pObj->hash(_size)].append(pObj);
  if (success) _total++;
  return success;
}


// "remove" removes the first occurrence of an object that isEqual
// to the specified object from the table.
//
Bool CmHashTable::remove(CmObject* pObj)
{
  if (!pObj) return FALSE;
  Bool success = _buckets[pObj->hash(_size)].remove(pObj, ownsObjects());
  if (success) _total--;
  return success;
}


// "lookup" returns the first occurrence of an object which isEqual
// to the specified object.
//
CmObject* CmHashTable::lookup(CmObject* pObj) const
{
  if (!pObj) return FALSE;
  return _buckets[pObj->hash(_size)].lookup(pObj);
}


// "contains" checks to see if an object that isEqual to the specified
// object exists in the table.
//
Bool CmHashTable::contains(CmObject* pObj) const
{
  if (!pObj) return FALSE;
  return (_buckets[pObj->hash(_size)].lookup(pObj) == NULL) ? FALSE : TRUE;
}


// "occurrences" returns the number of objects in the table
// isEqual to the specified object.
//
unsigned CmHashTable::occurrences(CmObject* pObj) const
{
  if (!pObj) return FALSE;
  CmHashTableIterator iterator(*this);
  unsigned            num = 0;
  while (!iterator.done())
    if (iterator.next()->isEqual(pObj)) num++;
  return num;
}


// "removeAll" removes all objects from the table.
//
void CmHashTable::removeAll()
{
  for (int ii = 0; ii < _size; ii++)
    _buckets[ii].removeAll(ownsObjects());
  _total = 0;
}


// "resize" resizes the hash table.
//
Bool CmHashTable::resize(unsigned newSize)
{
  if (newSize <= 0) newSize = 1;

  int           newTotal   = 0;
  CmHashBucket *newBuckets = new CmHashBucket[newSize];
  if (!newBuckets) return FALSE;

  CmHashTableIterator iterator(*this);
  while (!iterator.done())
  {
    CmObject *pObj = iterator.next();
    newBuckets[pObj->hash(newSize)].append(pObj);
    newTotal++;
  }

  delete[] _buckets;
  _size    = newSize;
  _buckets = newBuckets;
  _total   = newTotal;
  return TRUE;
}


// "isEmpty" checks to see if any objects are contained in this table.
//
Bool CmHashTable::isEmpty() const
{
  Bool empty = TRUE;
  int  ii    = 0;
  while (ii < _size && empty == TRUE)
    if (_buckets[ii].size() > 0) empty = FALSE;
  return empty;
}


// "newIterator" creates and returns a new hash table iterator.
//
CmIterator* CmHashTable::newIterator() const
{
  return new CmHashTableIterator(*this);
}


// "write" writes the array objects to the specified reserve file.
//
Bool CmHashTable::write(CmReserveFile& file) const
{
  if (!writeBase(file))    return FALSE;            // Write base container.
  if (!file.write(_total)) return FALSE;            // Write number of objects.

  Bool success  = TRUE;
  CmHashTableIterator iterator(*this);
  while (!iterator.done() && success)               // For each object.
    success = iterator.next()->writeObject(file);   // Write object.
  return success;
}


// "read" reads the array objects from the specified reserve file.
//
Bool CmHashTable::read(CmReserveFile& file)
{
  unsigned size = readBase(file);                 // Read base container.

  int total;
  if (!file.read(total)) return FALSE;            // Read number of objects.
  if (!resize(size))     return FALSE;            // Resize the table.

  removeAll();

  Bool success = TRUE;
  int  ii      = 0;
  while (ii < total && success)                   // For each object,
  {
    CmObject *pObj = CmObject::readObject(file);  // Read object.
    if (pObj) success = add(pObj); ii++;          // Add to table.
  }
  return success;
}


// "append" adds a new object to the end of this hash bucket.
//
Bool CmHashBucket::append(CmObject* pObj)
{
  CmHashNode *newnode = new CmHashNode(pObj);
  if (!newnode) return FALSE;

  if (!_first)
    _first = _last = newnode;
  else
  {
    _last->_next = newnode;
    _last        = newnode;
  }
  _size++;
  return TRUE;
}


// "contains" checks to see if an object that isEqual to the specified
// object exists in the bucket.
//
Bool CmHashBucket::contains(CmObject* pObj) const
{
  CmHashNode *rover = _first;
  Bool        found = FALSE;
  while (rover && !found)
  {
    if (rover->_data->isEqual(pObj)) found = TRUE;
    else                             rover = rover->_next;
  }
  return found;
}


// "remove" removes the first occurrence of an object that isEqual
// to the specified object from the bucket.
//
Bool CmHashBucket::remove(CmObject* pObj, Bool delFlag)
{
  if (!pObj || !_first) return FALSE;

  if (_first->_data->isEqual(pObj))         // Object is first in the list.
  {
    CmHashNode *temp = _first;
    if (_first == _last) _first = _last = NULL;
    else                 _first = _first->_next;
    _size--;
    if (delFlag) delete temp->_data;
    delete temp;
    return TRUE;
  }

  CmHashNode *rover1 = _first;              // Search for object in list.
  CmHashNode *rover2 = _last;

  while (rover1 != NULL && !(rover1->_data->isEqual(pObj)))
  {
    rover2 = rover1;
    rover1 = rover1->_next;
  }

  if (rover1 == NULL) return FALSE;         // Object was not found.

  if (rover1 == _last)                      // Object is last in list.
  {
    _last         = rover2;
    rover2->_next = NULL;
  }

  else                                      // Remove object from list.
    rover2->_next = rover2->_next->_next;

  if (delFlag) delete rover1->_data;        // Delete object (if requested)
  delete rover1;                            // and delete the hash node.
  return TRUE;
}


// "lookup" returns the first occurrence of an object which isEqual
// to the specified object.
//
CmObject* CmHashBucket::lookup(CmObject* pObj) const
{
  CmHashNode *rover = _first;
  Bool        found = FALSE;
  while (rover && !found)
  {
    if (rover->_data->isEqual(pObj)) found = TRUE;
    else                             rover = rover->_next;
  }

  return (found) ? rover->_data : NULL;
}


// "removeAll" removes all objects from this list and deletes the objects
// if requested to do so.
//
void CmHashBucket::removeAll(Bool delFlag)
{
  CmHashNode *temp, *rover = _first;
  while (rover)
  {
    temp = rover->_next;
    if (delFlag) delete rover->_data;
    delete rover;
    rover = temp;
  }
  _size  = 0;
  _first = _last = NULL;
}


// "CmHashTableIterator" is the iterator constructor.
//
CmHashTableIterator::CmHashTableIterator(const CmHashTable& T)
                    : _table(T), _bucket(0), _node(NULL)
{
  while (_table._buckets[_bucket]._size == 0 && _bucket < _table._size)
    _bucket++;
  if (_bucket < _table._size) _node = _table._buckets[_bucket]._first;
}


// "next" returns the current object pointed to by the iterator and
// then advances the iterator to the next object.
//
CmObject* CmHashTableIterator::next()
{
  if (!_node) return NULL;

  CmObject *pObj = _node->_data;

  if (_node->_next)
    _node = _node->_next;
  else
  {
    _bucket++;
    while (_bucket < _table._size && _table._buckets[_bucket]._size == 0)
      _bucket++;
    _node = (_bucket < _table._size) ? _table._buckets[_bucket]._first : NULL;
  }
  return pObj;
}


// "previous" decrements the iterator by one object and then returns
// that object.
//
CmObject* CmHashTableIterator::previous()
{
  if (!_node) return NULL;
  CmObject *rval = _node->_data;

  if (_node == _table._buckets[_bucket]._first)
  {
    --_bucket;
    while (_bucket >= 0 && _table._buckets[_bucket]._size == 0) _bucket--;
    _node = (_bucket >= 0) ? _table._buckets[_bucket]._last : NULL;
  }
  else
  {
    CmHashNode *rover = _table._buckets[_bucket]._first;
    while (rover && rover->_next != _node)
      rover = rover->_next;
    _node = rover;
  }
  return rval;
}


// "first" moves the iterator to the first object in the table.
//
void CmHashTableIterator::first()
{
  _bucket = 0;
  _node   = NULL;
  while (_table._buckets[_bucket]._size == 0 && _bucket < _table._size)
    _bucket++;
  if (_bucket < _table._size) _node = _table._buckets[_bucket]._first;
}


// "last" moves the iterator to the last object in the table.
//
void CmHashTableIterator::last()
{
  _bucket = _table._size - 1;
  _node   = NULL;
  while (_bucket >= 0 && _table._buckets[_bucket]._size == 0)
    _bucket--;
  if(_bucket >= 0) _node = _table._buckets[_bucket]._last;
}